lib/Mi manual de algoritmos/version_actual/src/estructuras/segment_tree.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2 {\ttfamily \raggedright {
   3 \noindent
   4 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$vector$>$}} \\
   5 \mbox{}\textbf{\textcolor{Blue}{using}}\ \textbf{\textcolor{Blue}{namespace}}\ std\textcolor{BrickRed}{;} \\
   6 \mbox{} \\
   7 \mbox{}\textbf{\textcolor{Blue}{class}}\ \textcolor{ForestGreen}{SegmentTree}\textcolor{Red}{\{} \\
   8 \mbox{}\textbf{\textcolor{Blue}{public}}\textcolor{BrickRed}{:} \\
   9 \mbox{}\ \ vector\textcolor{BrickRed}{$<$}\textcolor{ForestGreen}{int}\textcolor{BrickRed}{$>$}\ arr\textcolor{BrickRed}{,}\ tree\textcolor{BrickRed}{;} \\
  10 \mbox{}\ \ \textcolor{ForestGreen}{int}\ n\textcolor{BrickRed}{;} \\
  11 \mbox{} \\
  12 \mbox{}\ \ \textbf{\textcolor{Black}{SegmentTree}}\textcolor{BrickRed}{()}\textcolor{Red}{\{\}} \\
  13 \mbox{}\ \ \textbf{\textcolor{Black}{SegmentTree}}\textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ vector\textcolor{BrickRed}{$<$}\textcolor{ForestGreen}{int}\textcolor{BrickRed}{$>$}\ \textcolor{BrickRed}{\&}arr\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{:}\ \textbf{\textcolor{Black}{arr}}\textcolor{BrickRed}{(}arr\textcolor{BrickRed}{)}\ \textcolor{Red}{\{} \\
  14 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{initialize}}\textcolor{BrickRed}{();} \\
  15 \mbox{}\ \ \textcolor{Red}{\}} \\
  16 \mbox{} \\
  17 \mbox{}\ \ \textit{\textcolor{Brown}{//must\ be\ called\ after\ assigning\ a\ new\ arr.}} \\
  18 \mbox{}\ \ \textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{initialize}}\textcolor{BrickRed}{()}\textcolor{Red}{\{} \\
  19 \mbox{}\ \ \ \ n\ \textcolor{BrickRed}{=}\ arr\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();} \\
  20 \mbox{}\ \ \ \ tree\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{resize}}\textcolor{BrickRed}{(}\textcolor{Purple}{4}\textcolor{BrickRed}{*}n\ \textcolor{BrickRed}{+}\ \textcolor{Purple}{1}\textcolor{BrickRed}{);} \\
  21 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{initialize}}\textcolor{BrickRed}{(}\textcolor{Purple}{0}\textcolor{BrickRed}{,}\ \textcolor{Purple}{0}\textcolor{BrickRed}{,}\ n\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{);} \\
  22 \mbox{}\ \ \textcolor{Red}{\}} \\
  23 \mbox{} \\
  24 \mbox{}\ \ \textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{query}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ query$\_$left\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ query$\_$right\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{const}}\textcolor{Red}{\{} \\
  25 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\ \textbf{\textcolor{Black}{query}}\textcolor{BrickRed}{(}\textcolor{Purple}{0}\textcolor{BrickRed}{,}\ \textcolor{Purple}{0}\textcolor{BrickRed}{,}\ n\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{,}\ query$\_$left\textcolor{BrickRed}{,}\ query$\_$right\textcolor{BrickRed}{);} \\
  26 \mbox{}\ \ \textcolor{Red}{\}} \\
  27 \mbox{} \\
  28 \mbox{}\ \ \textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{update}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ where\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ what\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  29 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{update}}\textcolor{BrickRed}{(}\textcolor{Purple}{0}\textcolor{BrickRed}{,}\ \textcolor{Purple}{0}\textcolor{BrickRed}{,}\ n\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{,}\ where\textcolor{BrickRed}{,}\ what\textcolor{BrickRed}{);} \\
  30 \mbox{}\ \ \textcolor{Red}{\}} \\
  31 \mbox{} \\
  32 \mbox{}\textbf{\textcolor{Blue}{private}}\textcolor{BrickRed}{:} \\
  33 \mbox{}\ \ \textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{initialize}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ node\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$left\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$right\textcolor{BrickRed}{);} \\
  34 \mbox{}\ \ \textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{query}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ node\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$left\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$right\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ query$\_$left\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ query$\_$right\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{const}}\textcolor{BrickRed}{;} \\
  35 \mbox{}\ \ \textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{update}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ node\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$left\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$right\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ where\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ what\textcolor{BrickRed}{);} \\
  36 \mbox{}\textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
  37 \mbox{} \\
  38 \mbox{}\textcolor{ForestGreen}{int}\ SegmentTree\textcolor{BrickRed}{::}\textbf{\textcolor{Black}{initialize}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ node\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$left\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$right\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  39 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}node$\_$left\ \textcolor{BrickRed}{==}\ node$\_$right\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  40 \mbox{}\ \ \ \ tree\textcolor{BrickRed}{[}node\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ node$\_$left\textcolor{BrickRed}{;} \\
  41 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\ tree\textcolor{BrickRed}{[}node\textcolor{BrickRed}{];} \\
  42 \mbox{}\ \ \textcolor{Red}{\}} \\
  43 \mbox{}\ \ \textcolor{ForestGreen}{int}\ half\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{(}node$\_$left\ \textcolor{BrickRed}{+}\ node$\_$right\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{/}\ \textcolor{Purple}{2}\textcolor{BrickRed}{;} \\
  44 \mbox{}\ \ \textcolor{ForestGreen}{int}\ ans$\_$left\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{initialize}}\textcolor{BrickRed}{(}\textcolor{Purple}{2}\textcolor{BrickRed}{*}node\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{,}\ node$\_$left\textcolor{BrickRed}{,}\ half\textcolor{BrickRed}{);} \\
  45 \mbox{}\ \ \textcolor{ForestGreen}{int}\ ans$\_$right\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{initialize}}\textcolor{BrickRed}{(}\textcolor{Purple}{2}\textcolor{BrickRed}{*}node\textcolor{BrickRed}{+}\textcolor{Purple}{2}\textcolor{BrickRed}{,}\ half\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{,}\ node$\_$right\textcolor{BrickRed}{);} \\
  46 \mbox{} \\
  47 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}arr\textcolor{BrickRed}{[}ans$\_$left\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$<$=}\ arr\textcolor{BrickRed}{[}ans$\_$right\textcolor{BrickRed}{])}\textcolor{Red}{\{} \\
  48 \mbox{}\ \ \ \ tree\textcolor{BrickRed}{[}node\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ ans$\_$left\textcolor{BrickRed}{;} \\
  49 \mbox{}\ \ \textcolor{Red}{\}}\textbf{\textcolor{Blue}{else}}\textcolor{Red}{\{} \\
  50 \mbox{}\ \ \ \ tree\textcolor{BrickRed}{[}node\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ ans$\_$right\textcolor{BrickRed}{;} \\
  51 \mbox{}\ \ \textcolor{Red}{\}} \\
  52 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ tree\textcolor{BrickRed}{[}node\textcolor{BrickRed}{];} \\
  53 \mbox{}\textcolor{Red}{\}} \\
  54 \mbox{} \\
  55 \mbox{}\textcolor{ForestGreen}{int}\ SegmentTree\textcolor{BrickRed}{::}\textbf{\textcolor{Black}{query}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ node\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$left\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$right\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ query$\_$left\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ query$\_$right\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{const}}\textcolor{Red}{\{} \\
  56 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}node$\_$right\ \textcolor{BrickRed}{$<$}\ query$\_$left\ \textcolor{BrickRed}{$|$$|$}\ query$\_$right\ \textcolor{BrickRed}{$<$}\ node$\_$left\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{;} \\
  57 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}query$\_$left\ \textcolor{BrickRed}{$<$=}\ node$\_$left\ \textcolor{BrickRed}{\&\&}\ node$\_$right\ \textcolor{BrickRed}{$<$=}\ query$\_$right\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\ tree\textcolor{BrickRed}{[}node\textcolor{BrickRed}{];} \\
  58 \mbox{} \\
  59 \mbox{}\ \ \textcolor{ForestGreen}{int}\ half\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{(}node$\_$left\ \textcolor{BrickRed}{+}\ node$\_$right\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{/}\ \textcolor{Purple}{2}\textcolor{BrickRed}{;} \\
  60 \mbox{}\ \ \textcolor{ForestGreen}{int}\ ans$\_$left\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{query}}\textcolor{BrickRed}{(}\textcolor{Purple}{2}\textcolor{BrickRed}{*}node\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{,}\ node$\_$left\textcolor{BrickRed}{,}\ half\textcolor{BrickRed}{,}\ query$\_$left\textcolor{BrickRed}{,}\ query$\_$right\textcolor{BrickRed}{);} \\
  61 \mbox{}\ \ \textcolor{ForestGreen}{int}\ ans$\_$right\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{query}}\textcolor{BrickRed}{(}\textcolor{Purple}{2}\textcolor{BrickRed}{*}node\textcolor{BrickRed}{+}\textcolor{Purple}{2}\textcolor{BrickRed}{,}\ half\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{,}\ node$\_$right\textcolor{BrickRed}{,}\ query$\_$left\textcolor{BrickRed}{,}\ query$\_$right\textcolor{BrickRed}{);} \\
  62 \mbox{} \\
  63 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}ans$\_$left\ \textcolor{BrickRed}{==}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\ ans$\_$right\textcolor{BrickRed}{;} \\
  64 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}ans$\_$right\ \textcolor{BrickRed}{==}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\ ans$\_$left\textcolor{BrickRed}{;} \\
  65 \mbox{} \\
  66 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{BrickRed}{(}arr\textcolor{BrickRed}{[}ans$\_$left\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$<$=}\ arr\textcolor{BrickRed}{[}ans$\_$right\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{?}\ ans$\_$left\ \textcolor{BrickRed}{:}\ ans$\_$right\textcolor{BrickRed}{);} \\
  67 \mbox{}\textcolor{Red}{\}} \\
  68 \mbox{} \\
  69 \mbox{}\textcolor{ForestGreen}{void}\ SegmentTree\textcolor{BrickRed}{::}\textbf{\textcolor{Black}{update}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ node\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$left\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ node$\_$right\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ where\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ what\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  70 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}where\ \textcolor{BrickRed}{$<$}\ node$\_$left\ \textcolor{BrickRed}{$|$$|$}\ node$\_$right\ \textcolor{BrickRed}{$<$}\ where\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\textcolor{BrickRed}{;} \\
  71 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}node$\_$left\ \textcolor{BrickRed}{==}\ where\ \textcolor{BrickRed}{\&\&}\ where\ \textcolor{BrickRed}{==}\ node$\_$right\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  72 \mbox{}\ \ \ \ arr\textcolor{BrickRed}{[}where\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ what\textcolor{BrickRed}{;} \\
  73 \mbox{}\ \ \ \ tree\textcolor{BrickRed}{[}node\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ where\textcolor{BrickRed}{;} \\
  74 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\textcolor{BrickRed}{;} \\
  75 \mbox{}\ \ \textcolor{Red}{\}} \\
  76 \mbox{}\ \ \textcolor{ForestGreen}{int}\ half\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{(}node$\_$left\ \textcolor{BrickRed}{+}\ node$\_$right\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{/}\ \textcolor{Purple}{2}\textcolor{BrickRed}{;} \\
  77 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}where\ \textcolor{BrickRed}{$<$=}\ half\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  78 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{update}}\textcolor{BrickRed}{(}\textcolor{Purple}{2}\textcolor{BrickRed}{*}node\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{,}\ node$\_$left\textcolor{BrickRed}{,}\ half\textcolor{BrickRed}{,}\ where\textcolor{BrickRed}{,}\ what\textcolor{BrickRed}{);} \\
  79 \mbox{}\ \ \textcolor{Red}{\}}\textbf{\textcolor{Blue}{else}}\textcolor{Red}{\{} \\
  80 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{update}}\textcolor{BrickRed}{(}\textcolor{Purple}{2}\textcolor{BrickRed}{*}node\textcolor{BrickRed}{+}\textcolor{Purple}{2}\textcolor{BrickRed}{,}\ half\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{,}\ node$\_$right\textcolor{BrickRed}{,}\ where\textcolor{BrickRed}{,}\ what\textcolor{BrickRed}{);} \\
  81 \mbox{}\ \ \textcolor{Red}{\}} \\
  82 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}arr\textcolor{BrickRed}{[}tree\textcolor{BrickRed}{[}\textcolor{Purple}{2}\textcolor{BrickRed}{*}node\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{]]}\ \textcolor{BrickRed}{$<$=}\ arr\textcolor{BrickRed}{[}tree\textcolor{BrickRed}{[}\textcolor{Purple}{2}\textcolor{BrickRed}{*}node\textcolor{BrickRed}{+}\textcolor{Purple}{2}\textcolor{BrickRed}{]])}\textcolor{Red}{\{} \\
  83 \mbox{}\ \ \ \ tree\textcolor{BrickRed}{[}node\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ tree\textcolor{BrickRed}{[}\textcolor{Purple}{2}\textcolor{BrickRed}{*}node\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{];} \\
  84 \mbox{}\ \ \textcolor{Red}{\}}\textbf{\textcolor{Blue}{else}}\textcolor{Red}{\{} \\
  85 \mbox{}\ \ \ \ tree\textcolor{BrickRed}{[}node\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ tree\textcolor{BrickRed}{[}\textcolor{Purple}{2}\textcolor{BrickRed}{*}node\textcolor{BrickRed}{+}\textcolor{Purple}{2}\textcolor{BrickRed}{];} \\
  86 \mbox{}\ \ \textcolor{Red}{\}} \\
  87 \mbox{}\textcolor{Red}{\}} \\
  88 \mbox{}
  89 } \normalfont\normalsize